\documentclass{beamer}
\usepackage{graphicx}
\usepackage{subfigure}

\setbeamertemplate{navigation symbols}{}
\setbeamercovered{dynamic}
\usetheme{Warsaw}
\logo{\includegraphics[scale=.2]{tiger.jpg}}


\newcommand{\plotslide}[4]{
\frame{\frametitle{#1}

#2

\vspace{-.5in}
\includegraphics[width=11cm]{#3}

#4

}
}

\newenvironment{changemargin}[3]{
\begin{list}{}{
\setlength{\topsep}{0pt}
\setlength{\leftmargin}{#1}
\setlength{\rightmargin}{#2}
\setlength{\topmargin}{#3}
\setlength{\listparindent}{\parindent}
\setlength{\itemindent}{\parindent}
\setlength{\parsep}{\parskip}
}
\item[]}{\end{list}}

\begin{document}

\title[DiGr: Directed Graph Processing Language]{DiGr: Directed Graph Processing Language}
\author[Golub, Oemler, Perepelitsa]{Ari Golub\\ Bryan Oemler\\ Dennis V. Perepelitsa} 
\institute{Columbia University\\COMS W4115: Programming Languages and Translators}
\date{22 December 2010\\Final Project Presentation}

% intro stuff
\frame{\titlepage}
%\logo{}

\frame{\frametitle{Introduction to DiGr}

\begin{itemize}

\item What can DiGr do?

\vfill

\begin{itemize}

\item Represent trees, graphs, walks, (mirrors, knots, etc).

\vfill

\item Model everything from basic computer science constructs to
  network-based problems in engineering and industry.

\vfill

\item Store information in nodes and edges without overhead or hassle.

\vfill 

\item Recursively or iteratively walk and modify directed graphs in
  user-specified ways.

\end{itemize}

\end{itemize}

}

\frame{\frametitle{Introduction to DiGr}

\begin{itemize}

\item What is the DiGr language / compiler like?

\vfill

\begin{itemize}

\item Imperative.

\vfill 

\item Compiled. Target language is C++, which is in turn compiled with
  {\tt g++} and linked against the DiGr backend.

\vfill

\item Statically (and locally) scoped.

\vfill

\item Specific graph-related objects (nodes, edges, walks) on top of a
  typed C-like base.

\vfill

\item Strongly typed.

\end{itemize}

\end{itemize}



}

\frame{\frametitle{Primitive types and opts}



\begin{itemize}

\item Integers, floating point numbers and strings are primitive types.

\vfill

{\tt 
  : this is a comment :\\
  str name = "Ari"!\\
  int age!\\
  age = 22!\\
  flt gpa = 4.0! : statements end with a ! :
}

\vfill

\item Opts have no return types, but have {\tt in} (not globally
  bound) and {\tt out} (in-scope from the program that called them)
  variables.

\vfill

{\tt 
opt times\_two(in int n; out int doubled)\{\\
\ \ \  doubled = n * 2!\\
\}
}

\end{itemize}

}


\frame{\frametitle{Nodes and edges}

\begin{itemize}

\item The high-level objects in DiGr are nodes and edges:

\vfill

{\tt 
  node n1!\\
  node n2!\\
  n1 -> n2! : n1 and n2 are now connected :
}

\vfill

\item Node and edge identifiers are handles. Edges are usually created anonymously:

\vfill

{\tt 
  edge e = n1.outedge(0)!\\
  node target = e.innode!
}

\end{itemize}

}


\frame{\frametitle{Connection contexts and attributes}

\begin{itemize}

\item Attributes are created as soon as they are referenced or assigned:

\vfill

{\tt 
  node city!\\
  city.population = 60000!\\
  print(city.population)! : prints 60000 :\\
  print(city.area)! : defaults to 0 :
}

\vfill

\item Connection contexts efficiently create graphs, and store the
  handles to the nodes in an array:

\vfill

{\tt 
  node binaryTree[7] = |3->(1->0,2),(5->4,6)| !
}

\end{itemize}

}


\frame{\frametitle{Crawls and rules}

\begin{itemize}

\item A {\tt crawl} is an opt run on a node, and can call a {\tt rule}
  that tells it where to go next.

\vfill

{\tt 
crawl markNode(in int marker) \{\\
\ \ \ current.mark = marker!\\
\ \ \ call! 
\}
}

\vfill

\item Rules modify the queue of nodes to visit when called:

\vfill

{\tt 
rule followLighterEdge\{\\
\ \ \ edge e1 = current.outedge(0)!\\
\ \ \ edge e2 = current.outedge(1)!\\
\ \ \ if (e1.weight < e2.weight)\\
\ \ \ \ \ \ \ \  \{ add(e1.child(0))! \}\\
\ \ \ else \{ add(e2.child(0))! \}\\
\}
}

\end{itemize}

}

\frame{\frametitle{DiGr in one slide}

{\tt
crawl printNode() \{ print(current.id)! call! \}\\
: print the node id and call the rule :
}

\vfill

{\tt rule preOrder \{ addByFront(node.id,$\tilde{}$,2)! \}\\
: add up to two children, smallest id first : }

\vfill

{\tt 
opt main() \{\\
\ \ \    node tree[5] = |3->(1->0,2),4| !\\
\ \ \    tree[0].id = 0! tree[1].id = 1! tree[2].id = 2!\\
\ \ \    tree[3].id = 3! tree[4].id = 4!\\
\ \ \    printNode() from tree[3] with preOrder!\\
\ \ \    : prints 3 1 0 2 4 :\\
\}
}

}


\frame{\frametitle{Compiler Front End}

\begin{center}
\includegraphics[width=11.5cm]{front.pdf}
\end{center}

\vfill

\begin{itemize}

\item Scanner turns DiGr program from standard input into
  tokens. Lexical correctness.

\vfill

\item Parser creates initial AST (nested OCaml tree of typed
  tuples). Syntactical correctness.

\vfill

\item Interpreter verifies AST. Semantic correctness.

\end{itemize}

}

\frame{\frametitle{Static Semantic Checking}

\begin{itemize}

\item The interpreter has several duties:

\vfill

\begin{itemize}

\item Create global scope for {\tt opt}/{\tt rule}/{\tt crawl} signatures.

\vfill

\item Create symbol table for all local scopes (inside functions and
  blocks).

\vfill

\item Check the scope of all identifiers.

\vfill

\item Check typing for all statements (recurse into expressions),
  including assignment, function calls, etc.

\end{itemize}

\vfill

\item After the front-end stage, intermediate representation of a
  sensible program (instance of DiGr AST).

\end{itemize}

}


\frame{\frametitle{Compiler Back End}

\begin{center}
\includegraphics[width=11.5cm]{back.pdf}
\end{center}

\vfill

\begin{itemize}

\item C++ AST: stripped-down, holds intermediate representation of C++
  program. A few shortcuts, but largely extensible. C++ AST assures
  {\em syntactical} correctness of output.

\vfill

\item Translator: converts DiGr AST to C++ AST. Does no semantic
  checking.

\vfill 

\item Compiler: crawls the C++ AST and outputs C++ code.

\vfill

\item g++: turns compiled DiGr code into an executable.

\end{itemize}

}

\frame{\frametitle{DiGr code pre-compilation}

{\tt \small
rule myrule \{\\
\ \ \   int n = 0!\\
\ \ \   while (n < current.outedges) \{\\
\ \ \ \ \ \      edge tmp\_edge = current.outedge(n)!\\
\ \ \ \ \ \      if (tmp\_edge.mark == 1) \{ \\
\ \ \ \ \ \ \ \ \        node destination = tmp\_edge.innode!\\
\ \ \ \ \ \ \ \ \        add(destination)!\\
\ \ \ \ \ \      \} \\
\ \ \ \ \ \      n = n + 1!\\
\ \ \   \}\\
\}\\

crawl thecrawl() \{\\
\ \ \   print (current.id)!\\
\ \ \   call!\\
\}

}

}

\frame{\frametitle{DiGr compiler output}

{\tt \tiny
\#include "digr.h"\\
\#include <iostream>\\

void myrule(DiGrNode *current, deque<DiGrNode*> *returnQueue) \{\\
int n =  0 ;\\
while(n < current->OutEdges())\\
\{DiGrEdge *tmp\_edge = current->getOutEdge(n);\\
if(tmp\_edge->getAttribute("mark") ==  1 )\\
\{DiGrNode *destination = tmp\_edge->inNode();\\
returnQueue->push\_back(destination);\\
\}\\


else\{\}\\
n=n +  1 ;\\
\}\\
\}\\

void thecrawl(DiGrNode *current, void (*rule)(DiGrNode*, deque<DiGrNode*>*)) \{\\
deque<DiGrNode*> *queue = new deque<DiGrNode*>();\\
queue->push\_back(current);\\
do \{\\
current=queue->front();\\
queue->pop\_front();\\
std::cout << current->getAttribute("id") << std::endl;\\
rule(current, queue);\\
\} while (queue->size() >  0 );\\
\}

}
%\end{Verbatim}

}

\frame{\frametitle{DiGr Test Plan}

\begin{itemize}

\item For each test program, we have a {\em gold standard} that
  execution should output. Every build, we compile and execute all
  tests and compare output with the gold standard.

\vfill

\item Test atomic DiGr elements from low-level (basic types,
  arithmetic, function calls, etc.) to high-level (graphs, attributes,
  connection contexts, etc.).

\vfill

\item Test programs which integrate a wide cross-section of features.

\vfill

\item Test errors at compilation (really, the interpret stage), and at run-time.

\end{itemize}

}

\end{document}
